#include "bits/stdc++.h"
using namespace std;
namespace HashTool {
  struct Barrett {
    using u32 = unsigned int;
    using u64 = unsigned long long;
    using u128 = unsigned __int128_t;
    static constexpr u128 s = u128(1) << 96;

    Barrett(const u32 P) : p_(P), m_((s - 1) / P + 1){}

    u32 div(u64 v) const {
      return (v * m_) >> 96;
    }

    u32 operator()(u64 v) {
      return v - u64(div(v)) * p_;
    }

    u128 m_;
    u32 p_;
  };

  using hashv = pair<int, int>;
  static int mod1 = 1000000009;
  static int mod2 = 1000000011;
  static int bas1 = 991723;
  static int bas2 = 991811;
  static Barrett fmd1(1000000009);
  static Barrett fmd2(1000000011);
  static vector<hashv> power_;
    
  hashv operator+(const hashv lhs, const int rhs) {
    int lv = lhs.first + rhs;
    int rv = lhs.second + rhs;
    if (lv >= mod1) {
      lv -= mod1;
    }
    if (rv >= mod2) {
      rv -= mod2;
    }
    return {lv, rv};
  }

  hashv operator-(const hashv lhs, const int rhs) {
    int lv = lhs.first - rhs;
    int rv = lhs.second - rhs;
    if (lv < 0) {
      lv += mod1;
    }
    if (rv < 0) {
      rv += mod2;
    }
    return {lv, rv};
  }

  hashv operator-(const hashv lhs, const hashv rhs) {
    int lv = lhs.first - rhs.first;
    int rv = lhs.second - rhs.second;
    if (lv < 0) {
      lv += mod1;
    }
    if (rv < 0) {
      rv += mod2;
    }
    return {lv, rv};
  }

  hashv operator*(const hashv lhs, const int rhs) {
    int lv = fmd1(1ll * lhs.first * rhs);
    int rv = fmd2(1ll * lhs.second * rhs);
    return {lv, rv};
  }

  hashv operator*(const hashv lhs, const hashv rhs) {
    int lv = fmd1(1ll * lhs.first * rhs.first);
    int rv = fmd2(1ll * lhs.second * rhs.second);
    return {lv, rv};
  }

  bool operator==(const hashv lhs, const hashv rhs) {
    if (lhs.first != rhs.first || lhs.second != rhs.second) {
      return false;
    }
    return true;
  }

  bool operator!=(const hashv lhs, const hashv rhs) {
    return !(lhs == rhs);
  }

  struct Hash {
    Hash(const char s[]) {
      n_ = strlen(s);
      hash_.resize(n_ + 1);

      hash_[0] = {0, 0};
      for (int i = 1; i <= n_; i++) {
        hash_[i] = hash_[i - 1] * hashv{bas1, bas2} + s[i - 1];
      }
    }

    hashv query(int l, int r) {
      assert(r <= n_ && l > 0 && l <= r);
      return hash_[r] - hash_[l - 1] * power_[r - l + 1];
    }

    vector<hashv> hash_;
    int n_;
  };

  void initPower(int n) {
    power_.resize(n + 1);
    power_[0] = {1, 1};

    for (int i = 1; i <= n; i++) {
      power_[i] = power_[i - 1] * hashv{bas1, bas2};
    }
  }
};
using namespace HashTool;
// 使用前先在main函数执行initPower
// initPower(1000000);
using namespace std;
int main() {
	initPower(6);
	Hash hs1 = Hash("abcdef");
	Hash hs2 = Hash("babc");
	cout << hs1.query(1, 3).first << endl;
	cout << hs2.query(2, 4).first << endl;
	return 0;
}